package top.fengleifeng.question;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import top.fengleifeng.util.ListNode;

/**
 * @author : fengelfeing
 * @version V1.0
 * @Project: leetcode-test
 * @Package : top.fengleifeng.question
 * @Description:
 * @Date: 2020年11月05日8:18 下午
 */
public class Z回文链表 {

    /**
     * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int x) { val = x; }
     * }
     */
    class Solution {

        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            ListNode one = head;
            ListNode two = head;
            while (two != null && two.next != null) {
                one = one.next;
                two = two.next.next;
            }
            ListNode now = null;
            ListNode nowEqual = null;
            if (two == null) {//偶数
                now = head;
                nowEqual = one;
            } else {//奇数
                now = head;
                nowEqual = one.next;
            }
            Stack<Integer> stack = new Stack<>();
            Queue<Integer> queue = new LinkedList<>();
            while (nowEqual != null) {
                stack.push(now.val);
                queue.add(nowEqual.val);
                now = now.next;
                nowEqual = nowEqual.next;
            }
            while (!stack.empty()) {
                Integer pop = stack.pop();
                Integer tw = queue.poll();
                if (pop.intValue() != tw.intValue()) {
                    return false;
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
//        ListNode listNode = new ListNode(1);
//        listNode.next = new ListNode(0);
//        listNode.next.next = new ListNode(1);

        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(2);
        listNode.next.next.next = new ListNode(1);
        boolean palindrome = new Z回文链表().new Solution().isPalindrome(listNode);
        System.out.println(palindrome);
    }
}
